<?php

/**
 * 堆排序
 *  堆排序(HeapSort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。
 *  可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。
 *  大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，
 *  因为根据大根堆的要求可知，最大的值一定在堆顶。
 *
 *  放在数组里，从0开始索引
 *  parent(i) floor($count/2) + 1
 *  $left       2 * $i + 1;
 *  $right      2 * $i + 2;
 *
 *
 * Class HeapSort
 */
class HeapSort
{
    public $count;
    
    public $data;
    
    /*
     * 初始化
     */
    public function __construct(array $arr)
    {
        $this->count = count($arr);
        $this->data  = $arr;
    }
    
    public function run()
    {
        $this->createHeap();
        while($this->count>0)
        {
            $this->swap($this->data[0],$this->data[--$this->count]);
            $this->buildHeap($this->data,0,$this->count);
        }
        
        return $this->data;
    }
    
    /**
     * 创建一个堆
     */
    public function createHeap()
    {
        $i = floor($this->count/2) + 1;
        while($i--)
        {
            $this->buildHeap($this->data,$i,$this->count);
        }
    }
    
    /**
     * 重建堆
     *
     * @param array $arr    数组
     * @param int   $i      父节点
     * @param int   $count  当前数据的元素
     *
     * @return mixed
     */
    public function buildHeap(&$arr,$i,$count)
    {
        if ($i > $count)
        {
            return;
        }
        
        $left  = 2 * $i + 1;
        $right = 2 * $i + 2;
        $max   = $i;
        
        //如果左子节点大于当前节点，记录左子节点的键名
        if ($left < $count && $arr[$i] < $arr[$left])
        {
            $max = $left;
        }
        
        //如果右子节点大于刚刚记录的$max , 那么再次交换，并记录右子节点的键名
        if ($right < $count && $arr[$max] < $arr[$right])
        {
            $max = $right;
        }
        
        //递归比较结束c条件
        if ($max !== $i && $max < $count)
        {
            $this->swap($arr[$i],$arr[$max]);
            $this->buildHeap($arr,$max,$count);
        }
    }
    
    /**
     * 交换
     *
     * @param int $left     交换的值
     * @param int $right    交换的值
     *
     * @return mixed
     *
     */
    public function swap(&$left,&$right)
    {
        list($left,$right) = array($right,$left);
    }
}

$arr = [1,2,3,43,121,12,-2,1,3,0.2,121,342];
var_dump((new HeapSort($arr))->run());